package 我的Java学习_算法基础.day_07;

import java.util.ArrayList;

/**
 * @author 挚爱之夕
 * @date 2021/8/20 - 08 - 20 - 14:07
 * @Description: 我的暑假Java学习.day_07
 * @Version: 1.0
 */
public class _111_全排列_上 {
    public static void main(String[] args) {
        String s = "abc";
        ArrayList<String> t = getPermutation1(s);
        System.out.println(t);
    }

    //迭代法
    public static ArrayList<String> getPermutation1(String A) {
        int n = A.length();
        ArrayList<String> res = new ArrayList<>();
        res.add(A.charAt(0) + "");

        for (int i = 1; i < n; i++) {
            ArrayList<String> res_new = new ArrayList<>();
            char c = A.charAt(i);//新字符
            for (String str : res) {//访问上一趟集合中的每个字符串
                //插入到每个位置，形成一个新串
                String newStr = c + str;//加在前面
                res_new.add(newStr);
                newStr = str + c;//加在后面
                res_new.add(newStr);
                //加中间
                for (int j = 1; j < str.length(); j++) {
                    newStr = str.substring(0, j) + c + str.substring(j);
                    res_new.add(newStr);
                }
            }
            res = res_new;
        }
        return res;
    }

    //递归法
    public static ArrayList<String> getPermutation2(String A, int index) {
        int n = A.length();
        ArrayList<String> now = new ArrayList<>();
        String temp;
        if (index == 0) {
            temp = A.charAt(0) + "";
            now.add(temp);
            return now;
        }
        ArrayList<String> old=getPermutation2(A, index - 1);
        char c = A.charAt(index);
        for (String e:old
             ) {
            temp = c+e;
            now.add(temp);
            temp=e+c;
            now.add(temp);
            for(int i =1;i<index;i++){
                temp = e.substring(0,i)+c+e.substring(i);
                now.add(temp);
            }
        }
        return now;
    }
}
